class Solution {
public:
  vector<string> letterCombinations(string digits) {

    map<char, string> mmp;
    vector<string> ans;
    mmp['2'] = "abc";
    mmp['3'] = "def";
    mmp['4'] = "ghi";
    mmp['5'] = "jkl";
    mmp['6'] = "mno";
    mmp['7'] = "pqrs";
    mmp['8'] = "tuv";
    mmp['9'] = "wxyz";

    dfs(digits, 0, mmp, "", ans);

    return ans;

  }

  void dfs(string &digits, int index, map<char, string> &mmp, string temp, vector<string> &ans){

    if(index >= digits.length() && !temp.empty()){
      ans.push_back(temp);
      return;
    }

    for(int i = 0; i < mmp[digits[index]].length(); ++i){
      temp.push_back(mmp[digits[index]][i]);
      dfs(digits, index + 1, mmp, temp, ans);
      temp.pop_back();
    }

  }

};
